#include "ALGraph.h"
#include<iostream>
#include<cstring>
using namespace std;
int i,j,k;  //循环变量

template<class DataType>
ALGraph<DataType>::ALGraph(DataType a[],int n,int e)
{
    VertexNum=n;
    arcNum=e;
    for(i=0; i<VertexNum; i++)
    {
        adjlist[i].vertex=a[i];
        adjlist[i].firstedge=NULL;
        adjlist[i].in=0;
    }
    ArcNode *s;
    for(k=0; k<arcNum; k++)
    {
        cin>>i>>j;
        s=new ArcNode;
        s->adjvex=j;
        s->next=adjlist[i].firstedge;
        adjlist[i].firstedge=s;
    }
}

template<class DataType>
void ALGraph<DataType>::DFSTraverse(int v)
{
    cout<<adjlist[v].vertex;
    visited[v]=1;
    ArcNode *p=adjlist[v].firstedge;
    while(p!=NULL)
    {
        j=p->adjvex;
        if(visited[j]==0)
            DFSTraverse(j);
        p=p->next;
    }
}

template<class DataType>
void ALGraph<DataType>::BFSTraverse(int v)
{
    int Q[100]= {0};
    int front,rear;
    front=rear=-1;
    cout<<adjlist[v].vertex;
    visited[v]=1;
    Q[++rear]=v;
    while(front!=rear)
    {
        v=Q[++front];
        ArcNode *p=adjlist[v].firstedge;
        while(p!=NULL)
        {
            j=p->adjvex;
            if(visited[j]==0)
            {
                cout<<adjlist[j].vertex;
                visited[j]=1;
                Q[++rear]=j;
            }
            p=p->next;
        }
    }

}

template<class DataType>
void ALGraph<DataType>::TopSort(ALGraph G)
{
    int S[100]= {0};
    int top=-1;
    int count=0;
    int j;
    for(i=0; i<G.VertexNum; i++)
        if(G.adjlist[i].in==0) S[++top]=i;
    while(top!=-1)
    {
        j=S[top--];
        cout<<G.adjlist[j].vertex;
        count++;
        ArcNode *p=G.adjlist[j].firstedge;
        while(p!=NULL)
        {
            k=p->adjvex;
            G.adjlist[k].in--;
            if(G.adjlist[k].in==0) S[++top]=k;
            p=p->next;
        }
    }
    if(count<G.VertexNum) cout<<"有回路";

}


int main()
{
    char a[9]= {'A','B','C','D','E','F','G','H','I'};
    ALGraph<char> G(a,9,11);
    memset(visited,0,sizeof(visited));
    G.BFSTraverse(0);
    cout<<endl;

    memset(visited,0,sizeof(visited));
    for(int i=0; i<9; i++)
        if(visited[i]==0)
            G.DFSTraverse(i);
    cout<<endl;

    G.TopSort(G);
    return 0;
}
/*
0 1
0 2
0 3
1 4
2 4
3 5
4 6
4 7
5 7
6 8
7 8
*/
